package backtracing;

import java.util.*;

/**
 * @author: june
 * @date: 2023/8/2
 * @description: 491. 递增子序列
 * 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
 * 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
 **/

public class NonDecreasingSubsequence_491 {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> sequence = new LinkedList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        backtrace(nums, 0);
        return result;
    }

    private void backtrace(int[] nums, int startIndex) {
        // 至少有2个元素才算是非递减序列
        if (sequence.size() >= 2) {
            result.add(new ArrayList<>(sequence));
        }
        // 终止条件
        if (startIndex >= nums.length) {
            return;
        }

        // 用来记录本层的元素是否被重复使用
        Set<Integer> hs = new HashSet<>();

        for (int i = startIndex; i < nums.length; i++) {
            // 如果非递增序列的最后一个元素大于数组的当前元素，则跳过
            // 如果数组的当前元素已经遍历过了，则跳过
            if (!sequence.isEmpty() && sequence.getLast() > nums[i] || hs.contains(nums[i])) {
                continue;
            }
            hs.add(nums[i]);
            sequence.add(nums[i]);
            backtrace(nums, i + 1);
            sequence.removeLast();
        }
    }

    public static void main(String[] args) {
        NonDecreasingSubsequence_491 subsequence491 = new NonDecreasingSubsequence_491();
        int[] nums = {4, 6, 7, 7};
        List<List<Integer>> lists = subsequence491.findSubsequences(nums);
        System.out.println(lists);
    }
}
